home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / ddjcompr / ashford / model.c < prev    next >
C/C++ Source or Header  |  1991-08-25  |  26KB  |  1,326 lines
  1. #include <stdio.h>
  2. #include <mem.h>
  3. #include <alloc.h>
  4. #include <stdlib.h>
  5.  
  6. #include "comp.h"
  7. #include "arith.h"
  8.  
  9.  
  10. #define MAX_CUM_FREQ   0x4000    /* maximum cumulative frequency */
  11.  
  12. struct model
  13.  
  14. {
  15.     int initial_level;
  16.     int match_level;
  17.  
  18.     unsigned base_count;
  19.     unsigned sym_freq;
  20.  
  21.     unsigned order_cum_freq [MAX_ORDER + 2];
  22.     unsigned order_sym_count [MAX_ORDER + 2];
  23. };
  24.  
  25.  
  26.  
  27. /*
  28.     Define circular dictionary large enough to hold complete
  29.     set of active input symbols.
  30.  
  31.     Extra entries are included in the dictionary corresponding
  32.     to a string of length equal to the maximum order to facilitate
  33.     searching across the end of the dictionary.  This extra space
  34.     is allocated at the front of the dictionary, so that the first
  35.     few entries are never referenced directly.
  36.  
  37.     An additional table is allocated consisting of one word entries
  38.     used to link equivalent dictionary entries where a hash table is
  39.     used to locate the start of each search chain.
  40.  
  41.     The last character of the test string is used locate the
  42.     initial hash table entry.  The hash table entries are stored
  43.     as an extension to the link table.
  44.  
  45.     The link table is accessed through the use of macros to allow
  46.     easy access to this table when its size excceds 64K.
  47. */
  48.  
  49. #ifndef FAR_TABLES
  50.  
  51. static unsigned char dict [MAX_DICT];
  52. static unsigned char base_level [MAX_DICT];
  53. static unsigned int next_dict [MAX_DICT + HTBL1_SIZE];
  54.  
  55. #define DICT_WORD_PTR(i) ((unsigned *) (&dict [i]));
  56. #define NEXT_DICT(i) next_dict [i]
  57.  
  58. #else
  59.  
  60. static unsigned char far *dict;
  61. static unsigned char far *base_level;
  62. #define DICT_WORD_PTR(i) ((unsigned far *) (&dict [i]));
  63.  
  64. #ifdef SPLIT_TABLES
  65.  
  66. static unsigned int far *next_dict [2];
  67. #define NEXT_DICT(i) next_dict [i & 1] [i >> 1]
  68.  
  69. #else
  70.  
  71. static unsigned int far *next_dict;
  72. #define NEXT_DICT(i) next_dict [i]
  73.  
  74. #endif
  75. #endif
  76.  
  77.  
  78. static unsigned int node;
  79. static int new_symbol_count;
  80. static unsigned int last_search_node;
  81.  
  82. static int max_order;
  83. static int max_pos_size;
  84.  
  85. /*
  86.     Define table of entries for each order giving number of symbols
  87.     and total cumulative frequency for each order
  88. */
  89.  
  90. static struct model active_state;
  91. static struct model last_state;
  92.  
  93.  
  94. /*
  95.     Define set of save areas for the state at the potential start any string
  96.     The areas are used in rotation until a substring is matched equal to
  97.     the minimum string length.  Normal symbol compression is performed
  98.     during the time that the substring matches the input data.
  99.         
  100.     When the first non matching character is encountered, the lengths of
  101.     the string and the compressed symbols are compared.  If the string
  102.     length is less, the output is repositioned as specified by the
  103.     state at the start of the string, and the string selection sequence
  104.     overwrites the output.
  105. */
  106.  
  107. static struct
  108.  
  109. {
  110.     int i;
  111.     struct coder_state cs;
  112.     struct model mod;
  113. } save_state [MAX_STR_SAVE];
  114.  
  115.  
  116. static int save_state_index;
  117. static unsigned int string_pos;
  118. static int string_len;
  119. static int string_start;
  120. static int skip_count;
  121.  
  122. /*
  123.     States used while testing for text string replacements
  124. */
  125.  
  126. static enum
  127. {
  128.     STRING_WAIT,  STRING_SEARCH,  STRING_START,  STRING_ACTIVE,
  129.     STRING_COMP,
  130. } string_state;
  131.  
  132.  
  133. /*
  134.     Define combined set of tables giving the order and
  135.     frequency count for each symbol encountered during dictionary scan
  136.     Also accumulate base frequency values for each order
  137. */
  138.  
  139. static unsigned char level [MAX_SYM];
  140. static unsigned int freq [MAX_SYM];
  141. static unsigned int base_freq [MAX_ORDER + 2];
  142.  
  143. static unsigned int dup_count = 0;
  144. static int dup_char = -1;
  145.  
  146. /*
  147.     Build frequency table for zero and default orders
  148.     Used to initialize state tables at start of each dictionary scan
  149.  
  150.     Always contains nonzero count for every symbol
  151.     Includes order for each symbol selecting zero or default orders
  152.     Initially set to all defaults with symbol frequency one
  153. */
  154.  
  155. static unsigned int sym_count_zero;
  156. static unsigned int cum_freq_zero;
  157. static unsigned int freq_zero [MAX_SYM];
  158. static unsigned char order_zero [MAX_SYM];
  159.  
  160.  
  161. /*
  162.     Prototypes
  163. */
  164.  
  165. static void clear_context (void);
  166. static void scan_dict (int);
  167. static void scale_freq_tbl (int, int);
  168. static void calc_symbol_freq (int);
  169. static void select_output_symbol (void);
  170. static int decode_symbol (void);
  171. static void update_model (int);
  172.  
  173. static void encode_symbol (struct model *);
  174. static void generate_switch_code (struct model *);
  175. static void generate_symbol_code (struct model *);
  176. static void generate_value (unsigned, unsigned);
  177.  
  178. static int start_decode_string (void);
  179. static int decode_active_state (void);
  180. static int decode_string_char (void);
  181. static unsigned decode_value (unsigned);
  182.  
  183. static unsigned switch_char_freq (unsigned, unsigned);
  184.  
  185. static void delete_dict_entry (int);
  186. static void test_string_state (void);
  187. static void clear_text_string (void);
  188.  
  189. static void check_string_cont (void);
  190. static void test_string_start (unsigned pos, int n);
  191. static void test_string_resume (unsigned pos, int n);
  192. static void replace_text_string (void);
  193.  
  194. static int log2 (unsigned);
  195. static void scale_binary_value (long, int *, unsigned *);
  196. static void update_bit_len (unsigned, unsigned, int *, unsigned *);
  197. static int find_string_len (void);
  198.  
  199.  
  200. /*
  201.     Initialize model at start of compression or expansion
  202.     Alocate and initialize tables
  203. */
  204.  
  205. void InitModel (int n)
  206.  
  207. {
  208.     unsigned i;
  209.  
  210.     InitCoder ();
  211.  
  212.     active_state.initial_level = 1;
  213.     node = MAX_ORDER;
  214.     max_pos_size = log2 (NDICT - 1) + 1;
  215.     max_order = n;
  216.     if (max_order == 0) max_order = 1;
  217.  
  218.     sym_count_zero = 0;
  219.     cum_freq_zero = 0;
  220.  
  221. #ifdef FAR_TABLES
  222.  
  223.     dict = farmalloc (MAX_DICT * sizeof (unsigned char));
  224.     base_level = farmalloc (MAX_DICT * sizeof (unsigned char));
  225.  
  226. #ifndef SPLIT_TABLES
  227.  
  228.     next_dict = farmalloc ((MAX_DICT + HTBL1_SIZE) * sizeof (unsigned int));
  229.  
  230.     if (dict == NULL || base_level == NULL || next_dict == NULL)
  231.     {
  232.         printf ("Memory allocation failure\n");
  233.         exit (EXIT_FAILURE);
  234.     }
  235.  
  236. #else
  237.  
  238.     next_dict [0] = farmalloc ((MAX_DICT + HTBL1_SIZE + 1) / 2 * sizeof (unsigned int));
  239.     next_dict [1] = farmalloc ((MAX_DICT + HTBL1_SIZE + 1) / 2 * sizeof (unsigned int));
  240.  
  241.     if (dict == NULL || base_level == NULL || next_dict [1] == NULL)
  242.     {
  243.         printf ("Memory allocation failure\n");
  244.         exit (EXIT_FAILURE);
  245.     }
  246.  
  247.     #endif  /* SPLIT_TABLES */
  248.  
  249. #endif    /* FAR_TABLES */
  250.  
  251.     for (i = 0; i < MAX_SYM; i ++)
  252.     {
  253.         freq_zero [i] = 1;
  254.         order_zero [i] = 0;
  255.     }
  256.  
  257.     for (i = 0; i < MAX_DICT + HTBL1_SIZE; i ++)
  258.         NEXT_DICT (i) = NIL_DICT_PTR;
  259.  
  260.     for (i = 0; i < MAX_DICT; i ++)
  261.     {
  262.         dict [i] = 0;
  263.         base_level [i] = 0;
  264.     }
  265.  
  266.     save_state_index = 0;
  267.     string_pos = 0;
  268.     string_len = 0;
  269.     string_start = 0;
  270.     skip_count = MIN_STR;
  271.     string_state = STRING_WAIT;
  272. }
  273.  
  274.  
  275.  
  276.  
  277. /*
  278.     Compress next symbol
  279. */
  280.  
  281. void CompressSymbol (int ch)
  282.  
  283. {
  284.     int i;
  285.     unsigned cfreq;
  286.  
  287.     if (string_state == STRING_ACTIVE) check_string_cont ();
  288.  
  289.     if (dup_count > max_order + 2)
  290.     {
  291.         ++ active_state.order_cum_freq [max_order + 1];
  292.         ++ freq [dup_char];
  293.  
  294.         if (ch != dup_char)
  295.         {
  296.             for (i = 0, cfreq = 0; i < ch; i ++)
  297.             {
  298.                 if (level [i] == level [ch]) cfreq += freq [i];
  299.             }
  300.             
  301.             base_freq [level [ch]] = cfreq;
  302.         }
  303.     }
  304.     else
  305.     {
  306.         clear_context ();
  307.         for (i = 0; i < max_order + 2; i ++) base_freq [i] = 0;
  308.         scan_dict (ch);
  309.     }
  310.  
  311.     for (i = 1; i <= active_state.initial_level; i ++)
  312.     {
  313.         while (active_state.order_cum_freq [i] > MAX_CUM_FREQ)
  314.             scale_freq_tbl (i, ch);
  315.     }
  316.  
  317.     test_string_state ();
  318.  
  319.     calc_symbol_freq (ch);
  320.     select_output_symbol ();
  321.     update_model (ch);
  322. }
  323.  
  324.  
  325.  
  326. /*
  327.     Expand next symbol from input stream
  328. */
  329.  
  330. int ExpandSymbol (void)
  331.  
  332. {
  333.     int ch;
  334.  
  335.     if (dup_count > max_order + 2)
  336.     {
  337.         ++ active_state.order_cum_freq [max_order + 1];
  338.         ++ freq [dup_char];
  339.     }
  340.     else
  341.     {
  342.         clear_context ();
  343.         scan_dict (0);
  344.     }
  345.  
  346.     ch = string_len == 0 ? decode_symbol () : decode_string_char ();
  347.     update_model (ch);
  348.     
  349.     return ch;
  350. }
  351.  
  352.  
  353.  
  354. /*
  355.     Update tables used by model for new symbol
  356.     Link new symbol into dictionary
  357.     Delete oldest symbol in dictionary, if required
  358.     Update zero order frequencies if no higher level context found
  359. */
  360.  
  361. static void update_model (int ch)
  362.  
  363. {
  364.     int n;
  365.  
  366.     NEXT_DICT (node) = NIL_DICT_PTR;
  367.     NEXT_DICT (last_search_node) = node;
  368.     last_search_node = node;
  369.  
  370.     if (active_state.match_level < 2)
  371.     {
  372.         cum_freq_zero ++;
  373.         if (order_zero [ch])
  374.             freq_zero [ch] ++;
  375.         else
  376.         {
  377.             order_zero [ch] = 1;
  378.             sym_count_zero ++;
  379.         }
  380.     }
  381.  
  382.     dict [node] = ch;
  383.     if (ch == dup_char)
  384.         dup_count ++;
  385.     else
  386.     {
  387.         dup_char = ch;
  388.         dup_count = 0;
  389.     }
  390.  
  391.     n = active_state.match_level;
  392.     if (n == 0) n = 1;
  393.     base_level [node] = n;
  394.  
  395.     delete_dict_entry (node + max_order);
  396.  
  397.     active_state.initial_level = active_state.match_level;
  398.     if (active_state.initial_level <= max_order)
  399.         active_state.initial_level ++;
  400.  
  401.     if (++ node == MAX_DICT)
  402.     {
  403.         node = MAX_ORDER;
  404.         for (n = 1; n <= max_order; n ++)
  405.             dict [MAX_ORDER - n] = dict [MAX_DICT - n];
  406.     }
  407. }
  408.  
  409.  
  410.  
  411. /*
  412.     Delete oldest symbol from dictionary
  413.     Update frequency counts if added for lower order
  414. */
  415.  
  416. static void delete_dict_entry (int i)
  417.  
  418. {
  419.     unsigned int n;
  420.     int j;
  421.  
  422.     n = i;
  423.     if (n >= MAX_DICT) n -= NDICT;
  424.  
  425.     switch (base_level [n])
  426.     {
  427.         case 0:
  428.             break;
  429.  
  430.         case 1:
  431.             j = dict [n];
  432.             cum_freq_zero --;
  433.             if (-- freq_zero [j] == 0)
  434.             {
  435.                 order_zero [j] = 0;
  436.                 freq_zero [j] = 1;
  437.                 sym_count_zero --;
  438.             }
  439.  
  440.         default:
  441.             j = dict [n - 1];
  442.             NEXT_DICT (j + MAX_DICT) = NEXT_DICT (n);
  443.             break;
  444.     }
  445. }
  446.  
  447.  
  448. /*
  449.     Initialize tables at start of dictionary scan
  450.     Establish counts based on low order tables
  451. */
  452.  
  453. static void clear_context (void)
  454.  
  455. {
  456.     int i;
  457.  
  458.     for (i = 2; i < max_order + 2; i ++)
  459.     {
  460.         active_state.order_sym_count [i] = 0;
  461.         active_state.order_cum_freq [i] = 0;
  462.     }
  463.  
  464.     active_state.order_sym_count [1] = sym_count_zero;
  465.     active_state.order_sym_count [0] = MAX_SYM - sym_count_zero;
  466.  
  467.     active_state.order_cum_freq [1] = cum_freq_zero;
  468.     active_state.order_cum_freq [0] = MAX_SYM - sym_count_zero;
  469.  
  470.     movmem (freq_zero, freq, sizeof freq);
  471.     movmem (order_zero, level, sizeof level);
  472. }
  473.  
  474.  
  475.  
  476. /*
  477.     Perform search of dictionary to locate active contexts
  478.     Accumulate freqencies for all symbols encounered
  479.     Use initial character of input string to select the starting table value
  480. */
  481.  
  482. static void scan_dict (int base_char)
  483.  
  484. {
  485.     unsigned int k;
  486.     unsigned int jnode;
  487.     int ch;
  488.     int n;
  489.  
  490.     last_search_node = dict [node - 1] + MAX_DICT;
  491.     jnode = NEXT_DICT (last_search_node);
  492.  
  493.     while (jnode != NIL_DICT_PTR)
  494.     {
  495.         ch = dict [jnode];
  496.         for (n = 2; n < max_order + 1; n ++)
  497.         {
  498.             if (dict [node - n] != dict [jnode - n]) break;
  499.         }
  500.  
  501.         switch (string_state)
  502.         {
  503.             case STRING_SEARCH:
  504.             case STRING_START:
  505.                 test_string_start (jnode, n);
  506.                 break;
  507.  
  508.             case STRING_COMP:
  509.                 test_string_resume (jnode, n);
  510.                 break;
  511.         }
  512.  
  513.         if (base_level [jnode] <= n)
  514.         {
  515.             k = level [ch];
  516.             if (k < n)
  517.             {
  518.                 active_state.order_cum_freq [k] -= freq [ch];
  519.                 active_state.order_sym_count [k] --;
  520.  
  521.                 active_state.order_cum_freq [n] ++;
  522.                 active_state.order_sym_count [n] ++;
  523.  
  524.                 if (ch < base_char)
  525.                 {
  526.                     base_freq [k] -= freq [ch];
  527.                     base_freq [n] ++;
  528.                 }
  529.  
  530.                 level [ch] = n;
  531.                 freq [ch] = 1;
  532.  
  533.                 if (n > active_state.initial_level) active_state.initial_level = n;
  534.             }
  535.             else
  536.             if (k == n)
  537.             {
  538.                 active_state.order_cum_freq [n] ++;
  539.                 freq [ch] ++;
  540.                 if (ch < base_char) base_freq [n] ++;
  541.             }
  542.         }
  543.  
  544.         last_search_node = jnode;
  545.         jnode = NEXT_DICT (jnode);
  546.     }
  547. }
  548.  
  549.  
  550.  
  551. /*
  552.     Test for continued text substring
  553.     Executed before the start of each dictionary scan during compression
  554. */
  555.  
  556. static void check_string_cont (void)
  557.  
  558. {
  559.     int j;
  560.  
  561.     j = string_pos + string_len;
  562.     if (j >= MAX_DICT) j -= NDICT;
  563.  
  564.     if (dict [node - 1] == dict [j])
  565.         string_len ++;
  566.     else
  567.         string_state = STRING_COMP;
  568. }
  569.  
  570.  
  571.  
  572. /*
  573.     Test for start of potential text substring
  574.     Executed during dictionary scan based on string state variable
  575. */
  576.  
  577. static void test_string_start (unsigned pos, int n)
  578.  
  579. {
  580.     if (n > MIN_STR)
  581.     {
  582.         string_pos = pos;
  583.         if (string_pos < MIN_STR + MAX_ORDER) string_pos += NDICT;
  584.         string_pos -= MIN_STR;
  585.         string_len = MIN_STR;
  586.         string_state = STRING_START;
  587.     }
  588. }
  589.  
  590.  
  591.  
  592. static void test_string_resume (unsigned pos, int n)
  593.  
  594. {
  595.     if (n > string_len + 1)
  596.     {
  597.         string_state = STRING_ACTIVE;
  598.         string_len ++;
  599.         string_pos = pos;
  600.         if (string_pos < string_len + MAX_ORDER) string_pos += NDICT;
  601.         string_pos -= string_len;
  602.     }
  603.     else
  604.     if (n == max_order + 1)
  605.     {
  606.         unsigned i2, j2, n2;
  607.  
  608.         i2 = node - max_order - 1;
  609.         j2 = pos - max_order - 1;
  610.  
  611.         for (n2 = max_order + 1; n2 <= string_len + 1; n2 ++)
  612.         {
  613.             if (i2 < MAX_ORDER) i2 += NDICT;
  614.             if (j2 < MAX_ORDER) j2 += NDICT;
  615.             if (dict [i2 --] != dict [j2 --]) break;
  616.         }
  617.  
  618.         if (n2 > string_len + 1)
  619.         {
  620.             string_state = STRING_ACTIVE;
  621.             string_len ++;
  622.             string_pos = pos;
  623.             if (string_pos < string_len + MAX_ORDER) string_pos += NDICT;
  624.             string_pos -= string_len;
  625.         }
  626.     }
  627. }
  628.  
  629.  
  630.  
  631. /*
  632.     Test status of text substring match procedure
  633.     Performed after each dictionary scan
  634. */
  635.  
  636. static void test_string_state (void)
  637.  
  638. {
  639.     switch (string_state)
  640.     {
  641.         case STRING_WAIT:
  642.             save_state [string_start].mod = active_state;
  643.             SaveCoderState (&save_state [string_start].cs);
  644.  
  645.             if (++ string_start == MAX_STR_SAVE) string_start = 0;
  646.             if (-- skip_count == 0) string_state = STRING_SEARCH;
  647.             break;
  648.  
  649.         case STRING_SEARCH:
  650.             save_state [string_start].mod = active_state;
  651.             SaveCoderState (&save_state [string_start].cs);
  652.             if (++ string_start == MAX_STR_SAVE) string_start = 0;
  653.             break;
  654.  
  655.         case STRING_ACTIVE:
  656.             if (string_len > MAX_STR)
  657.             {
  658.                 string_len --;
  659.                 clear_text_string ();
  660.             }
  661.             break;
  662.  
  663.         case STRING_COMP:
  664.             clear_text_string ();
  665.             break;
  666.     }
  667. }
  668.  
  669.  
  670.  
  671. /*
  672.     End of text substring
  673.     Test for minimum code length of dtring versus coded symbols
  674.     Reposition output and write string selection if less
  675.     Set up for start of next string
  676. */
  677.  
  678. static void clear_text_string (void)
  679.  
  680. {
  681.     int nbits;
  682.     int i;
  683.  
  684.     if (string_len >= MIN_STR)
  685.     {
  686.         nbits = find_string_len ();
  687.         if (nbits > 0)
  688.         {
  689.             replace_text_string ();
  690.  
  691.             i = node;
  692.             if (i <= string_len) i += NDICT;
  693.             i -= string_len + 1;
  694.         }
  695.     }
  696.  
  697.     save_state [string_start].mod = last_state;
  698.     SaveCoderState (&save_state [string_start].cs);
  699.  
  700.     if (++ string_start == MAX_STR_SAVE) string_start = 0;
  701.  
  702.     encode_symbol (&last_state);
  703.  
  704.     save_state [string_start].mod = active_state;
  705.     SaveCoderState (&save_state [string_start].cs);
  706.  
  707.     if (++ string_start == MAX_STR_SAVE) string_start = 0;
  708.     skip_count = MIN_STR - 2;
  709.     string_len = 0;
  710.  
  711.     string_state = STRING_WAIT;
  712. }
  713.  
  714.  
  715.  
  716. /*
  717.     Estimate size of string reference
  718.     Returns size relative to actual length used by coded symbols
  719. */
  720.  
  721. static int find_string_len (void)
  722.  
  723. {
  724.     int nbits;
  725.     unsigned f;
  726.  
  727.     struct model start_context;
  728.     unsigned i;
  729.     unsigned n;
  730.     unsigned j;
  731.     int m;
  732.     unsigned c1;
  733.  
  734.     nbits = 0;
  735.     f = 0;
  736.  
  737.     new_symbol_count = MAX_SYM;
  738.     m = save_state [string_start].mod.match_level;
  739.     start_context = save_state [string_start].mod;
  740.  
  741. /*
  742.     Accumulate switch characters for default context
  743.     Include start of string symbol
  744. */
  745.  
  746.     do
  747.     {
  748.         new_symbol_count -= start_context.order_sym_count [m];
  749.  
  750.         c1 = start_context.order_cum_freq [m];
  751.         n = switch_char_freq (start_context.order_sym_count [m], c1);
  752.  
  753.         update_bit_len (n, c1 + n, &nbits, &f);
  754.     } while (-- m > 0);
  755.  
  756.     c1 = start_context.order_cum_freq [0];
  757.     update_bit_len (1, c1, &nbits, &f);
  758.  
  759. /*
  760.     Include string length
  761. */
  762.  
  763.     nbits += 6;
  764.     if (string_len - MIN_STR >= 63) nbits += 8;
  765.  
  766. /*
  767.     Calculate relative location of start of string
  768.     Output as bit count and offset
  769. */
  770.  
  771.     update_bit_len (1, max_pos_size, &nbits, &f);
  772.  
  773.     i = string_pos + string_len;
  774.     if (i >= MAX_DICT) i -= NDICT;
  775.     j = i < node ? node - i - 1 : node + NDICT - 1 - i;
  776.     nbits += log2 (j);
  777.  
  778.     return CodeLength (&save_state [string_start].cs) - nbits;
  779. }
  780.  
  781.  
  782.  
  783. /*
  784.     Generate coded symbols for text substring
  785.     Used when string length is less length used by actual symbols
  786. */
  787.  
  788. static void replace_text_string (void)
  789.  
  790. {
  791.     struct model start_context;
  792.     unsigned n;
  793.     unsigned i, j;
  794.  
  795.     RestoreCoderState (&save_state [string_start].cs);
  796.  
  797.     new_symbol_count = MAX_SYM;
  798.     start_context = save_state [string_start].mod;
  799.  
  800. /*
  801.     Output switch codes for default context and start string symbol
  802. */
  803.  
  804.     start_context.match_level = 0;
  805.     start_context.base_count = start_context.order_cum_freq [0] - 1;
  806.     start_context.sym_freq = 1;
  807.  
  808.     encode_symbol (&start_context);
  809.  
  810. /*
  811.     Output string length
  812. */
  813.     n = string_len - MIN_STR;
  814.     if (n < MAX_STR_CODE - 1)
  815.         generate_value (n, MAX_STR_CODE);
  816.     else
  817.     {
  818.         generate_value (MAX_STR_CODE - 1, MAX_STR_CODE);
  819.         generate_value (n + 1 - MAX_STR_CODE, 256);
  820.     }
  821.  
  822. /*
  823.     Determine relative location of start of string
  824. */
  825.  
  826.     i = string_pos + string_len;
  827.     if (i >= MAX_DICT) i -= NDICT;
  828.     j = i < node ? node - i - 1 : node - i - 1 + NDICT;
  829.     n = 2;
  830.     if (j < 2)
  831.         i = 0;
  832.     else
  833.     {
  834.         for (i = 1; 2 * n <= j && n < 0x8000; i ++, n <<= 1);
  835.         j -= n;
  836.     }
  837.  
  838. /*
  839.     Output bit length of relative string location
  840. */
  841.  
  842.     generate_value (i, max_pos_size);
  843.  
  844. /*
  845.     Output string location in 8 bit pices if required
  846. */
  847.  
  848.     if (i > 8)
  849.     {
  850.         generate_value (j & 0xFF, 256);
  851.         j >>= 8;
  852.         n >>= 8;
  853.     }
  854.  
  855.     generate_value (j, n);
  856. }
  857.  
  858.  
  859. /*
  860.     Scale frequency tables if total cumulative frequency exceeds maximum
  861.     Also recalculates frequencies for current input symbol
  862. */
  863.  
  864. static void scale_freq_tbl (int order, int ch)
  865.  
  866. {
  867.     int i;
  868.     unsigned cfreq;
  869.     unsigned t;
  870.  
  871.     i = 0;
  872.     cfreq = 0;
  873.  
  874.     if (level [ch] == order)
  875.     {
  876.         for (; i < ch; i ++)
  877.         {
  878.             if (level [i] == order)
  879.             {
  880.                 t = (freq [i] + 1) >> 1;
  881.                 freq [i] = t;
  882.                 cfreq += t;
  883.             }
  884.         }
  885.  
  886.         base_freq [order] = cfreq;
  887.  
  888.         t = (freq [i] + 1) >> 1;
  889.         freq [i] = t;
  890.         i ++;
  891.  
  892.         cfreq += t;
  893.     }
  894.  
  895.     for (; i < MAX_CHAR_CODE; i ++)
  896.     {
  897.         if (level [i] == order)
  898.         {
  899.             t = (freq [i] + 1) >> 1;
  900.             freq [i] = t;
  901.             cfreq += t;
  902.         }
  903.     }
  904.  
  905.     active_state.order_cum_freq [order] = cfreq;
  906. }
  907.  
  908.  
  909. /*
  910.     Determine symbol frequency counts for coder
  911. */
  912.  
  913. static void calc_symbol_freq (int ch)
  914.  
  915. {
  916.     int i;
  917.  
  918.     active_state.match_level = level [ch];
  919.     active_state.sym_freq = freq [ch];
  920.  
  921.     if (active_state.match_level > 1)
  922.         active_state.base_count = base_freq [active_state.match_level];
  923.     else
  924.     {
  925.         active_state.base_count = 0;
  926.         for (i = 0; i < ch; i ++)
  927.         {
  928.             if (level [i] == active_state.match_level)
  929.                 active_state.base_count += freq [i];
  930.         }
  931.     }
  932. }
  933.  
  934.  
  935. /*
  936.     Select state structure containing symbol to be output
  937.     Generate coded symbol value if required
  938.  
  939.     Note that there is a one character delay during substring matching
  940.     so that the non matching character at end of string is not output
  941.     until after string replacement has occurred
  942. */
  943.  
  944. static void select_output_symbol (void)
  945.  
  946. {
  947.     switch (string_state)
  948.     {
  949.         case STRING_START:
  950.             last_state = active_state;
  951.             string_state = STRING_ACTIVE;
  952.             break;
  953.  
  954.         case STRING_ACTIVE:
  955.             encode_symbol (&last_state);
  956.             last_state = active_state;
  957.             break;
  958.  
  959.         default:
  960.             encode_symbol (&active_state);
  961.             break;
  962.     }
  963. }
  964.  
  965.  
  966. /*
  967.     Generate coded value for symbol defined by input state variable
  968.     State includes symbol frequencies and all values used by coder
  969. */
  970.  
  971. static void encode_symbol (struct model *cptr)
  972.  
  973. {
  974.     int i;
  975.  
  976.     new_symbol_count = MAX_SYM;
  977.     i = cptr -> match_level;
  978.     while (i < cptr -> initial_level)
  979.     {
  980.         new_symbol_count -= cptr -> order_sym_count [cptr -> initial_level];
  981.         generate_switch_code (cptr);
  982.         cptr -> initial_level --;
  983.     }
  984.  
  985.     new_symbol_count -= cptr -> order_sym_count [i];
  986.     generate_symbol_code (cptr);
  987. }
  988.  
  989.  
  990. /*
  991.     Generate code for switch character to select next lower context
  992.     Input consists of state variable for symbol
  993. */
  994.  
  995. static void generate_switch_code (struct model *cptr)
  996.  
  997. {
  998.     unsigned c1;
  999.     unsigned n, m;
  1000.  
  1001.     n = cptr -> initial_level;
  1002.     c1 = cptr -> order_cum_freq [n];
  1003.     m = switch_char_freq (cptr -> order_sym_count [n], c1);
  1004.  
  1005.     EncodeArith (c1, m, c1 + m);
  1006. }
  1007.  
  1008.  
  1009. /*
  1010.     Generate code for symbol defined by input state variable
  1011. */
  1012.  
  1013. static void generate_symbol_code (struct model *cptr)
  1014.  
  1015. {
  1016.     unsigned int c1, c2, c3;
  1017.     int n;
  1018.  
  1019.     n = cptr -> initial_level;
  1020.     c1 = cptr -> base_count;
  1021.     c2 = cptr -> sym_freq;
  1022.     c3 = cptr -> order_cum_freq [n];
  1023.  
  1024.     if (n > 0) c3 += switch_char_freq (cptr -> order_sym_count [n], c3);
  1025.  
  1026.     EncodeArith (c1, c2, c3);
  1027. }
  1028.  
  1029.  
  1030.  
  1031. /*
  1032.     Estimate frequency to be allocated to the switch character
  1033.     Use number of symbols referenced in current context and the
  1034.     number of unreferenced symbols so far
  1035.  
  1036.     Value should reflect probability of encountering a symbol
  1037.     already present in the active context
  1038. */
  1039.  
  1040. static unsigned switch_char_freq (unsigned scount, unsigned cmax)
  1041.  
  1042. {    unsigned n;
  1043.  
  1044.     n = (scount + 1) * new_symbol_count / (scount + new_symbol_count);
  1045.     if (n + cmax > MAX_CUM_FREQ) n = MAX_CUM_FREQ + 1 - cmax;
  1046.  
  1047.     return n;
  1048. }
  1049.  
  1050.  
  1051. /*
  1052.     End of compression procedure
  1053.     Terminate active substring processing
  1054.     Close arithmetic coder and flush output
  1055. */
  1056.  
  1057. void CloseModel (void)
  1058.  
  1059. {
  1060.     if (string_state == STRING_ACTIVE) clear_text_string ();
  1061.     CloseCoder ();
  1062. }
  1063.  
  1064.  
  1065.  
  1066. /*
  1067.     Decode next input symbol from input stream
  1068.     Test for context switch and repeat until non switch symbol encountered
  1069. */
  1070.  
  1071. static int decode_symbol (void)
  1072.  
  1073. {
  1074.     int ch;
  1075.  
  1076.     new_symbol_count = MAX_SYM;
  1077.     active_state.match_level = active_state.initial_level;
  1078.  
  1079.     new_symbol_count -= active_state.order_sym_count [active_state.match_level];
  1080.     ch = decode_active_state ();
  1081.  
  1082.     while (ch == SWITCH_SYM)
  1083.     {
  1084.         active_state.match_level --;
  1085.         new_symbol_count -= active_state.order_sym_count [active_state.match_level];
  1086.         ch = decode_active_state ();
  1087.     }
  1088.  
  1089.     if (ch == START_STRING) ch = start_decode_string ();
  1090.  
  1091.     return ch;
  1092. }
  1093.  
  1094.  
  1095.  
  1096. /*
  1097.     Start of string symbol encountered
  1098.     Extract string length and position from input stream
  1099.     Returns first character in string
  1100. */
  1101.  
  1102. static int start_decode_string (void)
  1103.  
  1104. {
  1105.     unsigned i, j, k;
  1106.     unsigned n;
  1107.  
  1108.     string_len = decode_value (MAX_STR_CODE);
  1109.     if (string_len == MAX_STR_CODE - 1) string_len += decode_value (256);
  1110.     string_len += MIN_STR;
  1111.  
  1112.     i = decode_value (max_pos_size);
  1113.     if (i == 0)
  1114.     {
  1115.         i = 2;
  1116.         j = decode_value (2);
  1117.     }
  1118.     else
  1119.     if (i > 8)
  1120.     {
  1121.         j = decode_value (256);
  1122.         i -= 8;
  1123.         n = 1 << i;
  1124.         k = decode_value (n);
  1125.         k += n;
  1126.         k <<= 8;
  1127.         j += k;
  1128.     }
  1129.     else
  1130.     {
  1131.         n = 1 << i;
  1132.         j = decode_value (n);
  1133.         j += n;
  1134.     }
  1135.  
  1136.     string_pos = node < j + MAX_ORDER ? node + NDICT - j : node - j;
  1137.  
  1138.     return decode_string_char ();
  1139. }
  1140.  
  1141.  
  1142.  
  1143. /*
  1144.     Locate next character in text substring
  1145.     Increment string pointers and decrement length
  1146.     Set parameters used for updating state variable
  1147. */
  1148.  
  1149. static int decode_string_char (void)
  1150.  
  1151. {
  1152.     int ch;
  1153.     unsigned int j;
  1154.  
  1155.     ch = dict [string_pos];
  1156.     active_state.match_level = level [ch];
  1157.  
  1158.     string_len --;
  1159.     if (++ string_pos == MAX_DICT) string_pos = MAX_ORDER;
  1160.  
  1161.     last_search_node = dict [node - 1] + MAX_DICT;
  1162.     j = NEXT_DICT (last_search_node);
  1163.  
  1164.     while (j != NIL_DICT_PTR)
  1165.     {
  1166.         last_search_node = j;
  1167.         j = NEXT_DICT (j);
  1168.     }
  1169.  
  1170.     return ch;
  1171. }
  1172.  
  1173.  
  1174. /*
  1175.     Extract next value from input stream
  1176.     Search frequency tables to convert to symbol
  1177.     Update arithmetic decoder using symbol frequencies
  1178. */
  1179.  
  1180. static int decode_active_state (void)
  1181.  
  1182. {
  1183.     unsigned c1, c2, c3;
  1184.     unsigned sym;
  1185.     unsigned m;
  1186.     int i;
  1187.     int n;
  1188.  
  1189.     n = active_state.match_level;
  1190.     c2 = active_state.order_cum_freq [n];
  1191.  
  1192.     while (c2 > MAX_CUM_FREQ)
  1193.     {
  1194.          scale_freq_tbl (n, END_OF_FILE);
  1195.         c2 = active_state.order_cum_freq [n];
  1196.     }
  1197.  
  1198.     m = n > 0 ? switch_char_freq (active_state.order_sym_count [n], c2) : 0;
  1199.     c3 = c2 + m;
  1200.  
  1201.     sym = DecodeArith (c3);
  1202.     if (sym < c2)
  1203.     {
  1204.         c1 = 0;
  1205.         for (i = 0; i < MAX_SYM; i ++)
  1206.         {
  1207.             if (level [i] == n)
  1208.             {
  1209.                 m = freq [i];
  1210.                 c1 += m;
  1211.                 if (sym < c1) break;
  1212.             }
  1213.         }
  1214.  
  1215.         c1 -= m;
  1216.     }
  1217.     else
  1218.     {
  1219.         c1 = c2;
  1220.         i = SWITCH_SYM;
  1221.     }
  1222.  
  1223.     UpdateDecoder (c1, m, c3);
  1224.  
  1225.     return i;
  1226. }
  1227.  
  1228.  
  1229.  
  1230. /*
  1231.     Generate coded output for a constant value within a fixed range
  1232.     Value is treated as a symbol with frequency one
  1233. */
  1234.  
  1235. static void generate_value (unsigned value, unsigned range)
  1236.  
  1237. {
  1238.     EncodeArith (value, 1, range);
  1239. }
  1240.  
  1241.  
  1242. /*
  1243.     Extract constant value within fixed range
  1244.     Each possible value is treated as symbol with frequency one
  1245. */
  1246.  
  1247. static unsigned decode_value (unsigned range)
  1248.  
  1249. {    unsigned value;
  1250.  
  1251.     value = DecodeArith (range);
  1252.     UpdateDecoder (value, 1, range);
  1253.  
  1254.     return value;
  1255. }
  1256.  
  1257.  
  1258.  
  1259. /*
  1260.     Determine integer value of base 2 logarithm of integer value
  1261.     Use smallest power of two less than input value
  1262. */
  1263.  
  1264. static int log2 (unsigned n)
  1265.  
  1266. {
  1267.     int i;
  1268.  
  1269.     for (i = 0; n > 1; i ++, n >>= 1);
  1270.     return i;
  1271. }
  1272.  
  1273.  
  1274.  
  1275. /*
  1276.     Scale binary value as part of log calulation
  1277.     Input is a binary fraction (32 bits, 16 binary places)
  1278.     Extract integer log to base 2
  1279.     Return fractional part and accumulate integer part
  1280. */
  1281.  
  1282. static void scale_binary_value (long x, int *nbits, unsigned *frac)
  1283.  
  1284. {
  1285.     int i;
  1286.  
  1287.     i = log2 ((unsigned) (x >> 16));
  1288.     *nbits += i;
  1289.     *frac = (unsigned) (x >> i);
  1290. }
  1291.  
  1292.  
  1293. /*
  1294.     Estimate bit size of arithmetic coded values
  1295.  
  1296.     Input consists of symbol frequency (p) and cumulative frequency (q)
  1297.     Actual bit size is log to base 2 of (q / p)
  1298.     
  1299.     Maintain intermediate values as:
  1300.     
  1301.         n + log2 (1 + f)
  1302.  
  1303.     where n is integer and f is the remainder (between 0 and 1.0)
  1304.     stored as a 16 bit binary fraction.
  1305.  
  1306.     The pair (nbits, frac) contains the starting value for the bit length
  1307.     This is updated to include the latest symbol size
  1308. */
  1309.  
  1310. static void update_bit_len (unsigned p, unsigned q, int *nbits, unsigned *frac)
  1311.  
  1312. {
  1313.     long x;
  1314.     unsigned f2;
  1315.  
  1316.     x = ((long) q << 16) / p;
  1317.     scale_binary_value (x, nbits, &f2);
  1318.  
  1319.     x = (long) f2 * (long) *frac;
  1320.     x >>= 16;
  1321.     x += f2;
  1322.     x += *frac;
  1323.     x += 0x10000L;
  1324.     scale_binary_value (x, nbits, frac);
  1325. }
  1326.